package sort

/**
思路：
快速排序实现的重点在于数组的拆分，通常我们将数组的第一个或者最后一个元素定义为比较元素，然后将数组中小于比较元素的数放到左边，将大于比较元素的放到右边，
这样我们就将数组拆分成了左右两部分：小于比较元素的数组；大于比较元素的数组。我们再对这两个数组进行同样的拆分，直到拆分到不能再拆分，数组就自然而然地以升序排列了。

时间复杂度：  O(nlogn)
空间复杂度：只涉及相邻元素的交换，是原地排序算法
算法稳定性：涉及到数据的交换，有可能破坏原来相等元素的位置排序，所以是不稳定的排序算法。
 */
func QuickSort(nums []int) {
	quickSort(nums, 0, len(nums) - 1)
}
func quickSort(nums []int, p int, r int) {
	// 递归终止条件
	if p >= r {
		return
	}
	// 获取分区位置
	q := partition(nums, p, r)
	// 递归分区（排序是在定位 pivot 的过程中实现的）
	quickSort(nums, p, q - 1)
	quickSort(nums, q + 1, r)
}
// 定位 pivot
func partition(nums []int, p int, r int) int {
	// 以当前数据序列最后一个元素作为初始 pivot
	pivot := nums[r]
	// 初始化 i、j 下标
	i := p
	// 后移 j 下标的遍历过程
	for j := p; j < r; j++ {
		// 将比 pivot 小的数丢到 [p...i-1] 中，剩下的 [i...j] 区间都是比 pivot 大的
		if nums[j] < pivot {
			// 互换 i、j 下标对应数据
			nums[i], nums[j] = nums[j], nums[i]
			// 将 i 下标后移一位
			i++
		}
	}
	// 最后将 pivot 与 i 下标对应数据值互换
	// 这样一来，pivot 就位于当前数据序列中间，i 也就是 pivot 值对应的下标
	nums[i], nums[r] = pivot, nums[i]
	// 返回 i 作为 pivot 分区位置
	return i
}